import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-11-23
 * Time:21:49
 */
//TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大,但是k一般比较小 / 求数据中第K大/第K小的数据
//对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了。最佳的方式就是用堆来解决，基本思路如下：
//1. 用数据集合中前K个元素来建堆 - 前k个最大的元素，则建小堆    、   前k个最小的元素，则建大堆
//2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足(不是最小/最大)则替换堆顶元素
//将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
//(以上的求前K个最大/最小元素的思路，也适用于求第K个最大/最小的元素-堆顶元素就是第K个最大/最小的元素)

//示例：Top-K:有N个元素，找出前K个最小的元素
//方法1 - 整体排序        方法2 - 整体建立一个大小为N的小根堆
//方法3 - 把前k个元素创建为大根堆，遍历剩下的N-K个元素，和堆顶元素比较，如果比堆顶元素小，则堆顶元素删除，当前元素入堆(最好的做法)
class BigHeap implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class Top_K {
    //方法2
    public int[] smallestK1(int[] arr,int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        //整体建立一个小根堆   O(n*log_2n)
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        //实例化一个数组ret，存放堆中前k个最小的元素  O(k*log_2n)
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();//将前k个堆顶元素出堆，存放到ret中
        }

        return ret;//返回ret数组
    }

    //方法3
    public int[] smallestK(int[] arr,int k) {
        //实例化一个数组ret，存放堆中前k个最小的元素
        int[] ret = new int[k];
        //判空
        if (arr == null || k == 0) {
            return ret;
        }
        //将数组中前k个元素建立成一个大根堆  O(k*log_2k)
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,new BigHeap());
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //将除了数组前k个之外的所有元素与大根堆的堆顶元素比较，如果元素比堆顶元素小，则将堆顶元素删除，将此时的元素插入到堆中，此时会自动将其重新
        //调整成大根堆，然后继续让数组中的下一个元素与新的堆顶元素比较，直到数组中的元素全部与堆顶元素比较完成，此时的堆中存放的就是数组中前k个最小
        //的元素        O((n-k)*log_2k)
        for (int i = k; i < arr.length; i++) {
            int peekVal = priorityQueue.peek();
            if (arr[i] < peekVal) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        //将前k个堆顶元素出堆，存放到ret中
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;//返回ret数组
    }

    public int[] bigestK1(int[] arr,int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new BigHeap());
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
    public int[] bigestK(int[] arr,int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int peekVal = priorityQueue.peek();
            if (arr[i] >peekVal) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    //第K个最小的元素
    public int the_K_smallest(int[] arr,int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new BigHeap());
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int peekVal = priorityQueue.peek();
            if (arr[i] < peekVal) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        return priorityQueue.poll();
    }

    //第K个最大的元素
    public int the_K_biggest(int[] arr,int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int peekVal = priorityQueue.peek();
            if (arr[i] > peekVal) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        return priorityQueue.poll();
    }
}
